#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

//基本定义
#define eps 1e-8
#define zero(x) (((x)>0?(x):(-(x)))<eps)
#define sign(x) ((x)>eps?1:((x)<-eps?2:0))
#define sq(x) ((x)*(x)) 

struct point{
	double x, y;	
	point(double x=0, double y=0):x(x), y(y){}
	double dis(point t){return sqrt(sq(x-t.x) + sq(y-t.y));}
	double len(){return sqrt(sq(x) + sq(y));}
	point operator-(point t)const{return point(x-t.x, y-t.y);} 
	double dm(point t)const{return x*t.x + y*t.y;}
	double xm(point t)const{return x*t.y - t.x*y;}
	void input(){scanf("%lf%lf", &x, &y);}
};

//两点间距离
double dis(point a, point b){
	double x = b.x - a.x, y = b.y - a.y;
	return sqrt(x*x + y*y);
}	

//叉积
double xmult(point s, point e, point o){
	return (s.x-o.x)*(e.y-o.y) - (e.x-o.x)*(s.y-o.y);	
}

//判定凸多边形，顶点按顺时针或逆时针给出，允许相邻边共线
int is_convex(int n, point* p){
	int i, s[3] = {1, 1, 1};
	for (i=0; i<n && s[1]|s[2]; i++)
		s[sign(xmult(p[(i+1)%n], p[(i+2)%n], p[i]))] = 0;
	return s[1]|s[2];
}

//判定凸多边形，顶点按顺时针或逆时针给出，不允许相邻边共线
int is_convex_v2(int n, point* p){
	int i, s[3] = {1, 1, 1};
	for (i=0; i<n && s[0] && s[1]|s[2]; i++)
		s[sign(xmult(p[(i+1)%n], p[(i+2)%n], p[i]))] = 0;
	return s[0] && s[1]|s[2];
}

//求两条直线交点，用的时候必须保证两条直线不共线（平行）
point cross_ll(point ua, point ub, point va, point vb){
	point ret=ua;
	double t=((ua.x-va.x)*(va.y-vb.y)-(ua.y-va.y)*(va.x-vb.x))
			/((ua.x-ub.x)*(va.y-vb.y)-(ua.y-ub.y)*(va.x-vb.x));
	ret.x+=(ub.x-ua.x)*t;
	ret.y+=(ub.y-ua.y)*t;
	return ret;
}

//点到直线的距离
double dis_ptol(point q, point p1, point p2){
	return fabs(xmult(q, p1, p2))/dis(p1, p2);
}

//判断点是否在线段l上
int dot_online_in(point p, point p1, point p2){
	return zero(xmult(p, p1, p2)) && (p1.x-p.x)*(p2.x-p.x) < eps && (p1.y-p.y)*(p2.y-p.y) < eps	;
}

//判断点是否在任意多边形内，on_edge为1表示可以在多边形边上，为0不可以
int inside_polygon(point q, int n, point* p, int on_edge = 1){
	int cnt = 0;
	point s(q.x-1, q.y);
	p[n] = p[0];
	for(int i=0; i<n; i++){
		if(dot_online_in(q, p[i], p[i+1]))return on_edge;
		if(zero(p[i].y - p[i+1].y))continue;
		double a = xmult(p[i], s, q), b = xmult(p[i+1], s, q);
		int t = sign(a*b);
		if(!t){
			if(p[i].y > p[i+1].y && p[i].x < q.x && zero(a))cnt++;
			if(p[i+1].y > p[i].y && p[i+1].x < q.x && zero(b))cnt++;
		}else if(t==2){
			point tmp(cross_ll(s, q, p[i], p[i+1]));
			if((q.x - tmp.x) > 0)cnt++;	
		}
	}
	return cnt&1;
}

//凸包排序
int cmp(const point& a, const point& b){
	double r = xmult(a, b, p[0]);
	if(r > eps)return 1;
	if(zero(r))return dis(a, p[0]) < dis(b, p[0]);
	return 0;
}

//判定p1、p2是否在l1l2的两侧
bool opposite_side(point p1, point p2, point l1, point l2){
	return xmult(l1, p1, l2)*xmult(l1, p2, l2) < -eps;
}

//判定线段是否在任意多边形内（端点在多边形上认为是在多边形内）
int inside_polygon(point p1, point p2, int n, point* p){
	point t[MV], tp;
	int i, j, k=0;
	if (!inside_polygon(p1, n, p) || !inside_polygon(p2, n, p))return 0;
	p[n] = p[0];
	for (i=0; i<n; i++){
		if (opposite_side(p1, p2, p[i], p[i+1]) && opposite_side(p[i], p[i+1], p1, p2))
			return 0;
		else if (dot_online_in(p1, p[i], p[i+1]))
			t[k++] = p1;
		else if (dot_online_in(p2, p[i], p[i+1]))
			t[k++] = p2;
		else if (dot_online_in(p[i], p1, p2))
			t[k++] = p[i];
	}
	for(i=0; i<k; i++){
		for(j=i+1; j<k; j++){
			tp.x = (t[i].x+t[j].x)/2;
			tp.y = (t[i].y+t[j].y)/2;
			if(!inside_polygon(tp, n, p))
				return 0;
		}
	}
	return 1;
}

//求逆时针凸包(make sure n>=2)
void make_convex(int n, point* p, int& m, point* cv){
	int u = 0;
	for(int i=1; i<n; i++)
		if(p[i].y < p[u].y || zero(p[i].y - p[u].y) && p[i].x < p[u].x)	
			u = i;
	if(u)swap(p[u], p[0]);
	sort(p+1, p+n, cmp);
	m = 0;
	cv[m++] = p[0];
	cv[m++] = p[1];
	
	for(int i=2; i<n; i++){
		while(m>1 && xmult(cv[m-1], p[i], cv[m-2]) < eps)m--;
		cv[m++] = p[i];
	}
}

//半平面交n^2模板（这里只写出了切割的部分），dir为1代表是顺时针，为0逆时针。q是结果点集，m是结果点集的大小，tp是辅助存放数组，三者均是全局变量。
void cut(point p1, point p2, bool dir){
	int cnt = 0;
	q[m] = q[0];
	for(int i=0; i<m; i++){
		double t1 = xmult(q[i], p2, p1), t2 = xmult(q[i+1], p2, p1);
		if(dir && t1 > -eps)tp[cnt++] = q[i];
		if(!dir && t1 < eps)tp[cnt++] = q[i];	
		if(t1*t2 < -eps)tp[cnt++] = cross_ll(p1, p2, q[i], q[i+1]);	
	}	
	for(int i=0; i<cnt; i++)
		q[i] = tp[i];
	m = cnt;
}

//点到直线的垂足
point perpendicular(point p0, point p1, point p2){
	double a = p2.y-p1.y, b = p1.x-p2.x, c = -p1.x*p2.y+p1.y*p2.x;
	printf("a = %lf, b = %lf, c = %lf\n", a, b, c);
	point ret;
	ret.x = (b*b*p0.x - a*b*p0.y - a*c)/(a*a+b*b);
	ret.y = (-a*b*p0.x + a*a*p0.y - b*c)/(a*a+b*b);
	return ret;
}

//不相交两个凸包的最小（大）距离，接收的是两个逆时针凸包
double dis_CC(int n, point* p, int m, point* q){
	int i=0, j=0;
	for(int k=1; k<n; k++)
		if(p[k].y < p[i].y || zero(p[k].y - p[i].y)&&p[k].x<p[i].x)i = k;
	for(int k=1; k<m; k++)
		if(q[k].y > q[j].y || zero(q[k].y - q[j].y)&&q[k].x>q[j].x)j = k;
	int fi=i, fj=j;
	double ans = inf;
	do{
		double t = (p[(i+1)%n] - p[i])*(q[j]-q[(j+1)%m]);
		if(t > eps)ans = min(ans, dis_ps(q[j], p[i], p[(i+1)%n])), i = (i+1)%n;
		else ans = min(ans, dis_ps(p[i], q[j], q[(j+1)%m])), j = (j+1)%m;
	}while(i!=fi || j!=fj);
	return ans;
}

int main(){
	return 0;	
}
